package q213

import (
	"strconv"
)

/**
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
*/
func rob(nums []int) int {

	var m map[string]int = map[string]int{}

	return recursion(nums, 0, len(nums)-1, m)
}

func recursion(nums []int, i int, j int, m map[string]int) int {

	key := strconv.Itoa(i) + "-" + strconv.Itoa(j)
	l := j - i + 1

	value, ok := m[key]
	if ok {
		return value
	}

	if l <= 0 {
		return 0
	}
	if l == 1 {
		return nums[i]
	}

	var n1 int
	var n2 int

	if l == 2 {
		n1 = nums[i]
		n2 = nums[j]
	} else {
		if i == 0 {
			n1 = nums[i] + recursion(nums, i+2, j-1, m)
		} else {
			n1 = nums[i] + recursion(nums, i+2, j, m)
		}
		n2 = recursion(nums, i+1, j, m)
	}

	var max int
	if n1 >= n2 {
		max = n1
	} else {
		max = n2
	}
	m[key] = max
	//log.Printf("%v %v %d",nums,m,max);
	return max
}
